package offer;

public class Offer42 {

    public int maxSubArray(int[] nums) {
        if (nums.length==0){
            return 0;
        }

        int tmp=nums[0];
        for (int i = 1; i < nums.length ; i++) {
            if (nums[i-1]>0) {
                nums[i]+=nums[i-1];
            }
            tmp=Math.max(tmp,nums[i]);
        }
        return  tmp;
    }


    public int maxSubArray1(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        int max=Integer.MIN_VALUE;
        int[] dp=new int[nums.length];
          dp[0]=nums[0];
        for (int i = 1; i < nums.length ; i++) {
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            max=Math.max(max,dp[i]);
        }
        return  max>dp[0]?max:dp[0];
    }

    //TODO:2023/7/23根据小红书题目进一步改进

    public int maxSubArray(int[] nums ,int target) {

        if (nums.length==0){
            return 0;
        }

        int tmp=nums[0];
        for (int i = 1; i < nums.length ; i++) {
            if (nums[i-1]>0) {
                nums[i]+=nums[i-1];
            }
            else {
                tmp=tmp+target;
            }
            tmp=Math.max(tmp,nums[i]);
        }
        return  tmp;
    }


//TODO:2023/7/23 gptschool 给出的答案
    public  static int getMax(int[] nums,int x){
//        int length = nums.length;
//        int maxSum=0;
//        int currentSum=0;
//        int maxEndingHere=0;
//        int maxSofar=0;
//        for (int i = 0; i < length; i++) {
//            currentSum+=nums[i];
//            maxEndingHere=Math.max(nums[i],maxEndingHere+nums[i]);
//            maxSofar=Math.max(maxSofar,maxEndingHere);
//            maxSum=Math.max(maxSum,currentSum);
//        }
//        return  Math.max(maxSum,maxSofar+x);
        int length = nums.length;
        int maxSum=0;
        int currentSum=0;
        int maxEndingHere=0;
        int maxSofar=0;
        for (int i = 0; i < length; i++) {
            currentSum+=nums[i];
            maxEndingHere=Math.max(nums[i],maxEndingHere+nums[i]);
            maxSofar=Math.max(maxSofar,maxEndingHere);
            maxSum=Math.max(maxSum,currentSum);
        }
        return  Math.max(maxSum,maxSofar+x);
    }


    // 计算最大连续子数组和
    public static int maxSubarraySumAfterOneModification(int[] arr, int x) {
        int n = arr.length;
        int maxEndingHere = arr[0]; // 当前连续子数组的最大和（包含最后一个元素）
        int maxSoFar = arr[0]; // 目前遍历过的连续子数组的最大和

        // 计算不修改元素时的最大连续子数组和
        for (int i = 1; i < n; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            System.out.println("-------------------maxEndingHere---------------------------");
            System.out.println(maxEndingHere);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
            System.out.println("-------------------maxSoFar---------------------------");
            System.out.println(maxSoFar);

        }

        // 计算允许修改一个元素时的最大连续子数组和
        int maxAfterModification = Integer.MIN_VALUE;
        maxEndingHere = 0;
        for (int i = 0; i < n; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            System.out.println("==================maxEndingHere==============");
            System.out.println(maxEndingHere);
            maxAfterModification = Math.max(maxAfterModification, maxEndingHere);
            System.out.println("================ maxAfterModification================");
            System.out.println(maxAfterModification);

        }

        // 检查是否有必要修改元素
        if (maxSoFar >= maxAfterModification) {
            return maxSoFar;
        } else {
            // 修改一个元素后的最大连续子数组和
            return maxAfterModification + x;
        }
    }


    public static void main(String[] args) {
        Offer42 offer42 = new Offer42();
        int[] arr={-1,-2,3};
        System.out.println(Offer42.maxSubarraySumAfterOneModification(arr, 10));

    }



}
